import java.util.ArrayList;
import java.util.List;

public class 并行课程III {
    //https://leetcode.cn/problems/parallel-courses-iii/description/
    //拓扑排序加上一点点的动态规划
    public int minimumTime(int n, int[][] relations, int[] time) {
        //构建入度表和图
        List<List<Integer>> graph = new ArrayList<>();
        int[] indegree = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        for(int[] num: relations){
            graph.get(num[0]).add(num[1]);
            indegree[num[1]]++;
        }
        int[] queue = new int[n];
        int l = 0;
        int r = 0;
        int[] cost = new int[n + 1];
        //返回值
        int ans = 0;
        //入度为0的入队
        for (int i = 1; i <= n; i++) {
            if(indegree[i] == 0){
                queue[r++] = i;
            }
        }
        while(l < r){
            //当前点
            int cur = queue[l++];
            //加上当前课程的时间
            cost[cur] += time[cur - 1];
            //加上当前课程的时间, 比较一下最大值
            ans = Math.max(cost[cur],ans);
            for (int next : graph.get(cur)){
                //下一节课存上一节课学完的最大值
                cost[next] = Math.max(cost[next],cost[cur]);
                if(--indegree[next] == 0){
                    //入度为0再加入
                    queue[r++] = next;
                }
            }
        }
        return ans;
    }
}
